//Sam.XIAO
#include <bits/stdc++.h>
using namespace std;

int getans(char *num) {
   char sbin[1024] = {0};
   int l = strlen(num), pos = 0;
   for (int i = 0; i < l; i++) num[i] -= '0';

   while (true) {
      bool isContinue = false;
      num[l] = 0;  // !!!
      for (int i = 0; i < l; i++) {
         if (num[i] % 2) num[i + 1] += 10;
         num[i] /= 2;
         if (num[i]) isContinue = true;
      }
      sbin[pos++] = num[l] / 10;
      if (!isContinue) break;
   }

   int binPos = 0, base = 2011, ans = 1;
   while (binPos < pos) {
      if (sbin[binPos++]) ans = (ans * base) % 10000;
      base = base * base % 10000;
   }
   return ans;
}

void work1() {
   int k;
   scanf("%d", &k);

   while (k--) {
      char s[300];
      memset(s, 0, sizeof(s));
      scanf("%s", s);
      printf("%d\n", getans(s));
   }
}

int main() {
   work1();
   return 0;
}
